package com.mdnote.jianzhi_offer.flash_back;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/10/13
 * @description 剑指 Offer 13. 机器人的运动范围
 */
public class Offer13 {

    public static void main(String[] args) {
        Offer13 offer13 = new Offer13();
        int count = offer13.movingCount(3, 1, 0);
        System.out.println(count);
    }

    private int[] dx = {0, 0, -1, 1};
    private int[] dy = {1, -1, 0, 0};

    public int movingCount(int m, int n, int k) {

        if (m == 0 || n == 0) {
            return -1;
        }

        if (k == 0) {
            return 1;
        }

        boolean[][] isVisited = new boolean[m][n];
        return _dfs(0, 0, k, isVisited);

    }

    private int _dfs(int row, int column, int k, boolean[][] visited) {

        // Terminator
        if (!canGo(row, column, k)) {
            return 0;
        }
        // Process
        visited[row][column] = true;
        // Drill down
        int sum = 1;
        for (int i = 0; i < dx.length; i++) {
            if (inBoard(row + dx[i], column + dy[i], visited) && !visited[row + dx[i]][column + dy[i]]) {
                sum += _dfs(row + dx[i], column + dy[i], k, visited);
            }
        }

        return sum;
    }

    private boolean inBoard(int row, int column, boolean[][] visited) {
        return row >= 0 && column >= 0 && row < visited.length && column < visited[0].length;
    }

    private boolean canGo(int m, int n, int k) {
        int sum = 0;

        while (m > 0) {
            sum += m % 10;
            m /= 10;
        }

        while (n > 0) {
            sum += n % 10;
            n /= 10;
        }

        return sum <= k;
    }
}
